{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Celebrity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #two-pointers #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #双指针 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCelebrity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #搜寻名人"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你是一个专业的狗仔，参加了一个 <code>n</code> 人派对，其中每个人被从 <code>0</code> 到 <code>n - 1</code> 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是：其他所有 <code>n - 1</code> 个人都认识他/她，而他/她并不认识其他任何人。</p>\n",
    "\n",
    "<p>现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B呀？” 的问题，以确定 A 是否认识 B。你需要在（渐近意义上）尽可能少的问题内来确定这位 “名人” 是谁（或者确定这里没有 “名人”）。</p>\n",
    "\n",
    "<p>在本题中，你可以使用辅助函数 <code>bool knows(a, b)</code> 获取到 A 是否认识 B。请你来实现一个函数 <code>int findCelebrity(n)</code>。</p>\n",
    "\n",
    "<p>派对最多只会有一个 “名人” 参加。若 “名人” 存在，请返回他/她的编号；若 “名人” 不存在，请返回 <code>-1</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/02/02/277_example_1_bold.PNG\" style=\"height: 181px; width: 186px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>graph = [\n",
    "  [1,1,0],\n",
    "  [0,1,0],\n",
    "  [1,1,1]\n",
    "]\n",
    "<strong>输出: </strong>1\n",
    "<strong>解释: </strong>有编号分别为 0、1 和 2 的三个人。graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人，而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。“名人” 是编号 1 的人，因为 0 和 2 均认识他/她，但 1 不认识任何人。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/02/02/277_example_2.PNG\" style=\"height: 192px; width: 193px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>graph = [\n",
    "  [1,0,1],\n",
    "  [1,1,0],\n",
    "  [0,1,1]\n",
    "]\n",
    "<strong>输出: </strong>-1\n",
    "<strong>解释: </strong>没有 “名人”\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == graph.length</code></li>\n",
    "\t<li><code>n == graph[i].length</code></li>\n",
    "\t<li><code>2 <= n <= 100</code></li>\n",
    "\t<li><code>graph[i][j]</code> 是 <code>0</code> 或 <code>1</code>.</li>\n",
    "\t<li><code>graph[i][i] == 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果允许调用 API <code>knows</code> 的最大次数为 <code>3 * n</code> ，你可以设计一个不超过最大调用次数的解决方案吗？</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-celebrity](https://leetcode.cn/problems/find-the-celebrity/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-celebrity](https://leetcode.cn/problems/find-the-celebrity/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[0,1,0],[1,1,1]]', '[[1,0,1],[1,1,0],[0,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        result = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(result, i):\n",
    "                result = i\n",
    "        for i in range(n):\n",
    "            if i != result:\n",
    "                if knows(i, result) and (not knows(result, i)):\n",
    "                    continue\n",
    "                else:\n",
    "                    return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:#bool knows(a, b)获取到 A 是否认识 B\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        for x in range(1, n):\n",
    "            if knows(candidate, x) == True:\n",
    "                candidate = x\n",
    "                #### 小于x的有2种情况\n",
    "                #（1）被人不知，if如果被人知，就抢到了candidate\n",
    "                #（2）认识了别人，if认识别人，就放弃了candidate\n",
    "        \n",
    "        for x in range(n):\n",
    "            if candidate == x:  #名人不认识anyone  但是自己还是认识的\n",
    "                continue\n",
    "            if knows(candidate, x) == True:\n",
    "                return -1       #名人不应该认识anyone\n",
    "            if knows(x, candidate) == False:\n",
    "                return -1       #anyone都应该认识名人\n",
    "        \n",
    "        return candidate\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        q=[]\n",
    "        for i in range(n):\n",
    "            q.append(i)\n",
    "        while len(q)>=2:\n",
    "            cand=q.pop(0)\n",
    "            other=q.pop(0)\n",
    "            if knows(cand,other) is True or knows(other,cand) is False:\n",
    "                q.insert(0,other)\n",
    "            else:\n",
    "                q.insert(0, cand)\n",
    "            # now we only have one candidates\n",
    "        cand= q.pop(0)\n",
    "        for other in range(n):\n",
    "            if other==cand:\n",
    "                continue\n",
    "            if  knows(other,cand) is False  or knows(cand,other) is True:\n",
    "                return -1\n",
    "        return cand\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        self.n = n\n",
    "        for i in range(n):\n",
    "            if self.is_celebrity(i):\n",
    "                return i\n",
    "        return -1\n",
    "   \n",
    "    def is_celebrity(self, i):\n",
    "        for j in range(self.n):\n",
    "            if i == j: continue \n",
    "            if knows(i, j) or not knows(j, i):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        # 1 1 1\n",
    "        # 1 1 0 \n",
    "        # 0 0 1\n",
    "        cand = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(cand, i):\n",
    "                cand = i\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i == cand:\n",
    "                continue\n",
    "\n",
    "            if not knows(i,cand) or knows(cand, i):\n",
    "                return -1\n",
    "        return cand\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        can = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(can, i):\n",
    "                can = i\n",
    "        for i in range(n):\n",
    "            if i == can:\n",
    "                continue\n",
    "            if not knows(i, can) or knows(can, i):\n",
    "                return -1\n",
    "        return can\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        q = list(range(n))\n",
    "\n",
    "        while len(q) > 1:\n",
    "            cand = q.pop()\n",
    "            other = q.pop()\n",
    "\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                q.append(other)\n",
    "            elif knows(other, cand) or not knows(cand, other):\n",
    "                q.append(cand)\n",
    "\n",
    "        cand = q.pop()\n",
    "        for other in range(n):\n",
    "            if other == cand:\n",
    "                continue\n",
    "            if not knows(other, cand) or knows(cand, other):\n",
    "                return -1\n",
    "        \n",
    "        return cand\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        # 假设名人是0\n",
    "        ans = 0\n",
    "        # 第一次遍历所有人，找到可能的名人编号\n",
    "        for i in range(1, n):\n",
    "            # 如果ans认识i，那么ans不是名人，i有可能是名人\n",
    "            if knows(ans, i):\n",
    "                ans = i\n",
    "\n",
    "        # 第二次遍历所有人，判断ans是否不认识其他所有人，其他所有人是否都认识ans\n",
    "        for i in range(n):\n",
    "            if ans == i:\n",
    "                continue\n",
    "            # 如果i不认识ans，或者ans认识i，那么ans也不是名人，返回-1\n",
    "            if not knows(i, ans) or knows(ans, i):\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        for x in range(1, n):\n",
    "            if knows(candidate, x) == True:\n",
    "                candidate = x\n",
    "                #### 小于x的有2种情况\n",
    "                #（1）被人不知，if如果被人知，就抢到了candidate\n",
    "                #（2）认识了别人，if认识别人，就放弃了candidate\n",
    "        \n",
    "        for x in range(n):\n",
    "            if candidate == x:  #名人不认识anyone  但是自己还是认识的\n",
    "                continue\n",
    "            if knows(candidate, x) == True:\n",
    "                return -1       #名人不应该认识anyone\n",
    "            if knows(x, candidate) == False:\n",
    "                return -1       #anyone都应该认识名人\n",
    "        \n",
    "        return candidate\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(candidate, i):\n",
    "                candidate = i\n",
    "        for j in range(n):\n",
    "            if candidate==j:\n",
    "                continue\n",
    "            if knows(candidate,j) or not knows(j, candidate):\n",
    "                return -1\n",
    "        return candidate\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        for x in range(1, n):\n",
    "            if knows(candidate, x) == True:\n",
    "                candidate = x \n",
    "        \n",
    "        for x in range(n):\n",
    "            if candidate == x:\n",
    "                continue \n",
    "            if knows(candidate, x) == True:\n",
    "                return -1\n",
    "            if knows(x, candidate) == False:\n",
    "                return -1\n",
    "        return candidate\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate=0\n",
    "        for x in range(1,n):\n",
    "            if knows(candidate,x)==True:\n",
    "                candidate=x\n",
    "        for x in range(n):\n",
    "            if candidate==x:\n",
    "                continue\n",
    "            if knows(candidate,x)==True:\n",
    "                return -1\n",
    "            if knows(x,candidate) ==False:\n",
    "                return -1\n",
    "        return candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        vis = [False]*n\n",
    "        for i in range(n):\n",
    "            if vis[i]: continue\n",
    "            flag = True\n",
    "            # i是不是名人，1，他不认识所有人 2所有人认识他\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    kij = knows(i,j)\n",
    "                    kji = knows(j,i)\n",
    "                    if not (kji and not kij):\n",
    "                        flag = False\n",
    "                        break\n",
    "                    if kij: vis[i]=True\n",
    "                    else: vis[j] = True\n",
    "                    if kji: vis[j] = True\n",
    "                    else: vis[i] = True\n",
    "            if flag:\n",
    "                return i\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        count = 0\n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            if self.iscelebrity(i,n):\n",
    "                count+=1\n",
    "                index = i\n",
    "        if count==0:\n",
    "            return -1\n",
    "        return index\n",
    "    \n",
    "    \n",
    "    def iscelebrity(self,i,n):\n",
    "        for j in range(n):\n",
    "            if knows(i,j)==0 and knows(j,i)==1:\n",
    "                pass\n",
    "            elif i==j:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "\n",
    "        candidate = 0 # 初始化第一个人为候选人\n",
    "        # 所有箭头指向的节点就是名人\n",
    "        # 贪心：如果真有一个名人，那任意找到的箭头的指向，都会指向那个名人，所以取第一个被指向的人作为名人\n",
    "        for x in range(1, n):\n",
    "            # 假如 candidate 认识 x, 那 x 就是我们潜在的 candidate\n",
    "            if knows(candidate, x):\n",
    "                candidate = x\n",
    "\n",
    "        # 验证 candidate x 是否符合条件\n",
    "        for x in range(n):\n",
    "            # 名人肯定认识自己，跳过\n",
    "            if candidate == x:\n",
    "                continue\n",
    "            # 如果名人还认识别人，说明他不是名人\n",
    "            if knows(candidate, x):\n",
    "                return -1\n",
    "            # 如果别人不认识名人，说明他不是名人\n",
    "            if not knows(x, candidate):\n",
    "                return -1\n",
    "\n",
    "        return candidate\n",
    "\n",
    "        \n",
    "\n",
    "        # graph = [[0] * n for _ in range(n)]\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if knows(i, j):\n",
    "        #             graph[i][j] = 1\n",
    "\n",
    "        # # print(sum(graph[1], axis=1))\n",
    "        # for i in range(n):\n",
    "        #     if sum(graph[i]) == 1:\n",
    "        #         colSum = 0\n",
    "        #         for j in range(n):\n",
    "        #             colSum += graph[j][i]\n",
    "        #         if colSum == n:\n",
    "        #             return i\n",
    "\n",
    "        # return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand = 0\n",
    "        for i in range(n):\n",
    "            if knows(cand, i):\n",
    "                cand = i\n",
    "        for i in range(n):\n",
    "            if cand != i and knows(cand, i):\n",
    "                return -1\n",
    "            if cand != i and not knows(i, cand):\n",
    "                return -1\n",
    "            \n",
    "        return cand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n):\n",
    "            if knows(res,i):\n",
    "                res = i\n",
    "        \n",
    "        for i in range(n):\n",
    "            if res==i:\n",
    "                continue\n",
    "            if knows(res,i) or not knows(i,res):\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        q = [i for i in range(n)]\n",
    "\n",
    "        while len(q) >= 2:\n",
    "            cand = q.pop(0); other = q.pop(0)\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                q.insert(0, other)\n",
    "            else:\n",
    "                q.insert(0, cand)\n",
    "        \n",
    "        cand = q[0]\n",
    "        for other in range(n):\n",
    "            if other != cand:\n",
    "                if not knows(other, cand) or knows(cand, other):\n",
    "                    return -1\n",
    "        \n",
    "        return cand\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(candidate, i):\n",
    "                candidate = i\n",
    "            else:\n",
    "                if not knows(i, candidate):\n",
    "                    candidate = i\n",
    "        for i in range(n):\n",
    "            if i != candidate:\n",
    "                if knows(candidate, i) or not knows(i, candidate): return -1\n",
    "        return candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        # for example 1: it ruled out id 0 and 2\n",
    "        for i in range(1, n):\n",
    "            if knows(candidate, i): #排除法\n",
    "                candidate = i # 要有答案也只会有一个i是答案\n",
    "\n",
    "        for i in range(n):\n",
    "            if i != candidate:\n",
    "                # 不认识别人\n",
    "                if knows(candidate, i): # not i, candidate\n",
    "                    return -1\n",
    "                # 别人必须认识我\n",
    "                if not knows(i, candidate): # must have\n",
    "                    return -1\n",
    "        return candidate\n",
    "\n",
    "          \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n):\n",
    "            if knows(res, i):\n",
    "                res = i\n",
    "        for i in range(n):\n",
    "            if i!=res:\n",
    "                if not knows(i,res) or knows(res,i):\n",
    "                    return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for x in range(1, n):\n",
    "            if knows(res, x):\n",
    "                res = x\n",
    "        for x in range(n):\n",
    "            if res == x:\n",
    "                continue\n",
    "            if knows(res, x) == True or knows(x, res) == False:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        #一看数据范围,噢,我最喜欢暴力搜索(但要加剪枝,不然超时)\n",
    "        #枚举哪一个是名人\n",
    "        for i in range(n):\n",
    "            cnt=0\n",
    "            for j in range(n):\n",
    "                if i==j: continue\n",
    "                if knows(i,j) or not knows(j,i): break\n",
    "            else: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "\n",
    "        not_famous = set()\n",
    "        candidate = set()\n",
    "        for i in range(n):\n",
    "            if i in not_famous:\n",
    "                continue\n",
    "\n",
    "            is_famous = True\n",
    "            for j in range(n):    \n",
    "                if i == j:\n",
    "                    continue\n",
    "                if knows(j, i):\n",
    "                    not_famous.add(j)\n",
    "                else:\n",
    "                    not_famous.add(i)\n",
    "                    is_famous = False\n",
    "                    break\n",
    "                if knows(i, j):\n",
    "                    not_famous.add(i)\n",
    "                    is_famous = False\n",
    "                    break\n",
    "            if is_famous:\n",
    "                candidate.add(i)\n",
    "        \n",
    "        if len(candidate) == 1:\n",
    "            return list(candidate)[0]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        ls = list(range(n))\n",
    "        while len(ls)>1:\n",
    "            a = ls.pop()\n",
    "            b = ls.pop()\n",
    "            if knows(a,b) and not knows(b,a):\n",
    "                ls.append(b)\n",
    "            elif not knows(a,b) and knows(b,a):\n",
    "                ls.append(a)\n",
    "        if not ls:\n",
    "            return -1\n",
    "        cand = ls.pop()\n",
    "        for i in range(n):\n",
    "            if i != cand:\n",
    "                if knows(cand, i) or not knows(i, cand):\n",
    "                    return -1\n",
    "        return cand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            ok = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if knows(i, j) or not knows(j, i):\n",
    "                    ok = False\n",
    "                    break\n",
    "            if ok:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        a = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(a, i) or not knows(i, a):\n",
    "                a = i\n",
    "        for i in range(n):\n",
    "            if i != a and knows(a, i) or not knows(i, a):\n",
    "                return -1\n",
    "        return a\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidate = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(candidate, i) or not knows(i, candidate):\n",
    "                candidate = i\n",
    "        for i in range(n):\n",
    "            if i != candidate:\n",
    "                if knows(candidate, i) or not knows(i, candidate): return -1\n",
    "        return candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        indrge = [0] * n\n",
    "        outdrge = [0] * n\n",
    "\n",
    "        wait = []\n",
    "        for i in range(n):\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                if knows(i, j):\n",
    "                    count += 1\n",
    "                    if count > 1:\n",
    "                        break\n",
    "            if j == n-1 and count == 1:\n",
    "                wait.append(i)\n",
    "        print(wait)\n",
    "        for idx in wait:\n",
    "            if all(knows(i, idx) for i in range(n)):\n",
    "                return idx\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        #indeg=[0]*n\n",
    "        #outdeg=[0]*n\n",
    "        s=set()\n",
    "        for i in range(n):\n",
    "            s.add(i)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and knows(i,j):\n",
    "                    s.remove(i)\n",
    "                    break\n",
    "        #print(indeg,outdeg)\n",
    "        print(s)\n",
    "        for i in range(n):\n",
    "            find=False\n",
    "            if i in s:\n",
    "                for j in range(n):\n",
    "                    if i!=j and not knows(j,i):\n",
    "                        find=True\n",
    "                        break\n",
    "                if not find:\n",
    "                    return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        q = []\n",
    "\n",
    "        for i in range(n):\n",
    "            q.append(i)\n",
    "\n",
    "        while len(q) >= 2:\n",
    "\n",
    "            a = q.pop(0)\n",
    "            b = q.pop(0)\n",
    "\n",
    "            if knows(a, b) and not knows(b, a):\n",
    "                q.append(b)\n",
    "            \n",
    "            else:\n",
    "                q.append(a)\n",
    "        \n",
    "        a = q.pop()\n",
    "\n",
    "        for i in range(n):\n",
    "            if i != a and (not knows(i, a) or knows(a, i)):\n",
    "                return -1\n",
    "        return a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        mk = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                if knows(i, j):\n",
    "                    mk[i] = -1\n",
    "                    break\n",
    "\n",
    "        for i in range(n):\n",
    "            if mk[i] == -1: continue\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if i==j:continue\n",
    "                if knows(j,i) is False: continue\n",
    "                cnt +=1\n",
    "            if cnt == n-1: return i\n",
    "\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        # # 1. find graph 2. count indegree, 3. count outdegree\n",
    "        # # celebrity: indegree == n-1 and outdegree == 0\n",
    "        # graph = defaultdict(set)\n",
    "        # indegree = [0] * n\n",
    "        # outdegree = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i != j: # no need to verify self recogniciton\n",
    "        #             if knows(i, j):\n",
    "        #                 graph[i].add(j)\n",
    "        #                 indegree[j] += 1\n",
    "        #                 outdegree[i] += 1\n",
    "        \n",
    "        # inset = set()\n",
    "        # outset = set()\n",
    "        # for i, deg in enumerate(indegree):\n",
    "        #     if deg == n-1:\n",
    "        #         inset.add(i)\n",
    "        \n",
    "        # for i, deg in enumerate(outdegree):\n",
    "        #     if deg == 0:\n",
    "        #         outset.add(i)\n",
    "        # # print(inset, outset)   \n",
    "        # out = list(inset.intersection(outset))\n",
    "\n",
    "        # return out[0] if len(out) != 0 else -1\n",
    "        # quicker way\n",
    "        result = 0\n",
    "        for i in range(1,n): # result not knowing anyonce\n",
    "            if knows(result, i): # i might be celebrity, we update\n",
    "                result = i\n",
    "            else:\n",
    "                continue # we know i must not be celevrity\n",
    "\n",
    "        for i in range(n):\n",
    "            if i != result:\n",
    "                # continue\n",
    "                if knows(result, i) or not knows(i , result):\n",
    "                    return -1\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand = 0\n",
    "        for i in range(1,n):\n",
    "            if knows(cand, i):\n",
    "                cand = i \n",
    "        \n",
    "        for i in range(n):\n",
    "            if cand == i:\n",
    "                continue\n",
    "            if knows(cand, i):\n",
    "                return -1\n",
    "            if knows(i, cand) == False:\n",
    "                return -1\n",
    "        return cand\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        flag = [ True for i in range(n) ]\n",
    "        remain = n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if knows(i, j):\n",
    "                    remain -= 1 if flag[i] else 0\n",
    "                    flag[i] = False\n",
    "                else:\n",
    "                    remain -= 1 if flag[j] else 0\n",
    "                    flag[j] = False\n",
    "                if remain <= 1:\n",
    "                    break\n",
    "            if remain <= 1:\n",
    "                break\n",
    "        if remain == 0:\n",
    "            return -1\n",
    "        idx = flag.index(True)\n",
    "        for j in range(n):\n",
    "            if j == idx:\n",
    "                continue\n",
    "            if knows(idx, j) or not knows(j, idx):\n",
    "                return -1\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            isCelebrity=True\n",
    "            for j in range(n):\n",
    "                if i == j :continue\n",
    "                if knows(i,j) or not knows(j,i):\n",
    "                    isCelebrity=False\n",
    "                    break\n",
    "            if isCelebrity:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        celebrity_candidate = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(celebrity_candidate, i):\n",
    "                celebrity_candidate = i\n",
    "        \n",
    "        # 第二步：验证名人候选\n",
    "        for i in range(n):\n",
    "            # 名人候选必须不认识任何人（除了他自己）\n",
    "            # 所有其他人必须认识名人候选\n",
    "            if (celebrity_candidate != i and knows(celebrity_candidate, i)) or not knows(i, celebrity_candidate):\n",
    "                return -1\n",
    "        \n",
    "        return celebrity_candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        ppl = set([i for i in range(n)])\n",
    "        k = n\n",
    "        while k > 1:\n",
    "            iterator = iter(ppl)\n",
    "            e1 = next(iterator)\n",
    "            e2 = next(iterator)\n",
    "            know1 = knows(e1,e2)\n",
    "            know2 = knows(e2,e1)\n",
    "\n",
    "            if know1:\n",
    "                if know2:\n",
    "                    ppl.remove(e1)\n",
    "                    ppl.remove(e2)\n",
    "                    k -= 2\n",
    "                else:\n",
    "                    ppl.remove(e1)\n",
    "                    k -= 1\n",
    "            else:\n",
    "                if know2:\n",
    "                    ppl.remove(e2)\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    ppl.remove(e1)\n",
    "                    ppl.remove(e2)\n",
    "                    k -= 2\n",
    "        if k == 0: return -1\n",
    "        e = ppl.pop()\n",
    "        for i in range(n):\n",
    "            if knows(i,e):\n",
    "                continue\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        for i in range(n):\n",
    "            if i == e: continue\n",
    "            if knows(e,i):\n",
    "                return -1\n",
    "            else:\n",
    "                continue\n",
    "        \n",
    "        return e\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        \n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        possible = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(possible, i):\n",
    "                # possible is impossible and i might be possible\n",
    "                possible = i\n",
    "\n",
    "        \n",
    "        # confirm\n",
    "        for i in range(n): # all others\n",
    "\n",
    "            # check if possible is wrong\n",
    "            if possible != i: # don't check self\n",
    "                if knows(possible, i) or not knows(i, possible):\n",
    "                    return -1\n",
    "\n",
    "        \n",
    "        return possible\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        possible = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if knows(possible, i):\n",
    "                possible = i\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i != possible: # no need to check self\n",
    "                if not knows(i, possible) or knows(possible, i): # as long as one of these is violated, we do possible is not celebrity\n",
    "                    return -1\n",
    "            \n",
    "        return possible\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 1. find graph 2. count indegree, 3. count outdegree\n",
    "        # # celebrity: indegree == n-1 and outdegree == 0\n",
    "        # graph = defaultdict(set)\n",
    "        # indegree = [0] * n\n",
    "        # outdegree = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i != j: # no need to verify self recogniciton\n",
    "        #             if knows(i, j):\n",
    "        #                 graph[i].add(j)\n",
    "        #                 indegree[j] += 1\n",
    "        #                 outdegree[i] += 1\n",
    "        \n",
    "        # inset = set()\n",
    "        # outset = set()\n",
    "        # for i, deg in enumerate(indegree):\n",
    "        #     if deg == n-1:\n",
    "        #         inset.add(i)\n",
    "        \n",
    "        # for i, deg in enumerate(outdegree):\n",
    "        #     if deg == 0:\n",
    "        #         outset.add(i)\n",
    "        # # print(inset, outset)   \n",
    "        # out = list(inset.intersection(outset))\n",
    "\n",
    "        # return out[0] if len(out) != 0 else -1\n",
    "        # quicker way\n",
    "        result = 0\n",
    "        for i in range(1,n): # result not knowing anyonce\n",
    "            if knows(result, i): # i might be celebrity, we update\n",
    "                result = i\n",
    "            else:\n",
    "                continue # we know i must not be celevrity\n",
    "\n",
    "        for i in range(n):\n",
    "            if i != result:\n",
    "                # continue\n",
    "                if knows(result, i) or not knows(i , result): # we check if result know anyone and if anyone not knowing him, if this is the case, this is not celevrity\n",
    "                    return -1\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        # 入度为n-1，出度为0\n",
    "        person = list(range(n))\n",
    "        # 暴力\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if knows(j,i) and not knows(i,j):\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "                if cnt == n-1:\n",
    "                    return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        possible = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if knows(possible, i):\n",
    "                possible = i\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i != possible: # no need to check self\n",
    "                if not knows(i, possible) or knows(possible, i): # as long as one of these is violated, we do possible is not celebrity\n",
    "                    return -1\n",
    "            \n",
    "        return possible\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 1. find graph 2. count indegree, 3. count outdegree\n",
    "        # # celebrity: indegree == n-1 and outdegree == 0\n",
    "        # graph = defaultdict(set)\n",
    "        # indegree = [0] * n\n",
    "        # outdegree = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i != j: # no need to verify self recogniciton\n",
    "        #             if knows(i, j):\n",
    "        #                 graph[i].add(j)\n",
    "        #                 indegree[j] += 1\n",
    "        #                 outdegree[i] += 1\n",
    "        \n",
    "        # inset = set()\n",
    "        # outset = set()\n",
    "        # for i, deg in enumerate(indegree):\n",
    "        #     if deg == n-1:\n",
    "        #         inset.add(i)\n",
    "        \n",
    "        # for i, deg in enumerate(outdegree):\n",
    "        #     if deg == 0:\n",
    "        #         outset.add(i)\n",
    "        # # print(inset, outset)   \n",
    "        # out = list(inset.intersection(outset))\n",
    "\n",
    "        # return out[0] if len(out) != 0 else -1\n",
    "        # quicker way\n",
    "        result = 0\n",
    "        for i in range(1,n): # result not knowing anyonce\n",
    "            if knows(result, i): # i might be celebrity, we update\n",
    "                result = i\n",
    "            else:\n",
    "                continue # we know i must not be celevrity\n",
    "\n",
    "        for i in range(n):\n",
    "            if i != result:\n",
    "                # continue\n",
    "                if knows(result, i) or not knows(i , result): # we check if result know anyone and if anyone not knowing him, if this is the case, this is not celevrity\n",
    "                    return -1\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        #一看数据范围,噢,我最喜欢暴力搜索(但要加剪枝,不然超时)\n",
    "        #枚举哪一个是名人\n",
    "        for i in range(n):\n",
    "            cnt=0\n",
    "            for j in range(n):\n",
    "                if i==j: continue\n",
    "                if knows(i,j): break\n",
    "                if knows(j,i): cnt+=1\n",
    "                else: break\n",
    "            if cnt==n-1: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            ok = True\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if knows(i, j) or not knows(j, i):\n",
    "                    ok = False\n",
    "                    break\n",
    "            if ok:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand=[]\n",
    "        for i in range(n):\n",
    "            cand.append(i)\n",
    "        while len(cand)>=2:\n",
    "            cand1=cand.pop()\n",
    "            cand2=cand.pop()\n",
    "            if knows(cand1,cand2) or not knows(cand2,cand1):\n",
    "                cand.insert(0,cand2)\n",
    "            else:\n",
    "                cand.insert(0,cand1)\n",
    "        cele=cand.pop()\n",
    "        for i in range(n):\n",
    "            if i==cele:\n",
    "                continue\n",
    "            if knows(cele,i) or not knows(i,cele):\n",
    "                return -1\n",
    "        return cele"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        candidates = [i for i in range(n)]\n",
    "        while True:\n",
    "            u = candidates[0]\n",
    "            to_remove = set()\n",
    "            for v in candidates[1:]:\n",
    "                u_v = knows(u, v)\n",
    "                v_u = knows(v, u)\n",
    "                if u_v and not v_u:\n",
    "                    to_remove.add(u)\n",
    "                elif v_u and not u_v:\n",
    "                    to_remove.add(v)\n",
    "                else:\n",
    "                    to_remove.add(u)\n",
    "                    to_remove.add(v)\n",
    "            for v in to_remove:\n",
    "                candidates.remove(v)\n",
    "            if len(candidates) == 0:\n",
    "                return -1\n",
    "            if len(to_remove) == 0:\n",
    "                break\n",
    "        if len(candidates) != 1:\n",
    "            return -1\n",
    "        cand = candidates[0]\n",
    "        print(cand)\n",
    "        for i in range(n):\n",
    "            if i == cand or (knows(i, cand) and not knows(cand, i)):\n",
    "                continue\n",
    "            return -1\n",
    "        return cand\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        res = 0 \n",
    "        for i in range(1,n):\n",
    "            if knows(res,i):\n",
    "                res = i\n",
    "        for i in range(0,n):\n",
    "            if res==i: continue\n",
    "            if knows(res,i) or not knows(i,res): return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        memo = [1] * n\n",
    "        possible = []\n",
    "        for i in range(n):\n",
    "            if memo[i] == 0:\n",
    "                # i cannot be celebrity\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if i != j:\n",
    "                    if not knows(i,j):\n",
    "                        # i do not know j, j not celebrity\n",
    "                        memo[j] = 0\n",
    "                    else:\n",
    "                        # i know j: i not celebrity\n",
    "                        memo[i] = 0\n",
    "                        break\n",
    "                possible.append(i)\n",
    "        for pos in possible:\n",
    "            if memo[pos] == 0:\n",
    "                continue\n",
    "            cbty = True\n",
    "            for k in range(n):\n",
    "                if k != pos:\n",
    "                    if not knows(k,pos):\n",
    "                        cbty = False\n",
    "                        break\n",
    "            if cbty:\n",
    "                return pos\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            q.append(i)\n",
    "        \n",
    "        while len(q) > 1:\n",
    "            i = q.pop(0)\n",
    "            j = q.pop(0)\n",
    "\n",
    "            if knows(i, j):\n",
    "                q.insert(0, j)\n",
    "            elif not knows(i, j):\n",
    "                q.insert(0, i)\n",
    "            elif knows(j, i):\n",
    "                q.insert(0, i)\n",
    "            elif not knows(j, i):\n",
    "                q.insert(0, j)\n",
    "            \n",
    "        for i in range(n):\n",
    "            if i == q[0]: continue\n",
    "            if not knows(i, q[0]):\n",
    "                return -1\n",
    "            if knows(q[0], i):\n",
    "                return -1\n",
    "        return q[0]\n",
    "            \n",
    "\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     # 判断当前的第i个人是否是名人\n",
    "        #     flag = True\n",
    "        #     for j in range(n):\n",
    "        #         if i == j: continue\n",
    "        #         # print(f\"knows = {knows(i, j)}\")\n",
    "        #         if knows(i, j):\n",
    "        #             flag = False\n",
    "        #             break\n",
    "        #         if not knows(j, i):\n",
    "        #             flag = False\n",
    "        #             break\n",
    "        #     if flag:\n",
    "        #         return i\n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand = 0\n",
    "        for other in range(1, n):\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                cand = other\n",
    "\n",
    "        for other in range(n):\n",
    "            if other == cand:\n",
    "                continue\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                return -1\n",
    "        return cand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        #一看数据范围,噢,我最喜欢暴力搜索\n",
    "        #枚举哪一个是名人\n",
    "        for i in range(n):\n",
    "            cnt=0\n",
    "            for j in range(n):\n",
    "                if i==j: continue\n",
    "                if knows(i,j): break\n",
    "                if knows(j,i): cnt+=1\n",
    "                else: break\n",
    "            if cnt==n-1: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand = 0 \n",
    "        for other in range(1, n):\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                cand = other\n",
    "         \n",
    "        for i in range(n):\n",
    "            if cand == i:\n",
    "                continue \n",
    "            if knows(cand, i) or not knows(i, cand):\n",
    "                return -1 \n",
    "        return cand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand = 0\n",
    "        for other in range(1, n):\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                cand = other\n",
    "            else:\n",
    "                pass\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i == cand:\n",
    "                continue\n",
    "            elif not knows(i, cand) or knows(cand, i):\n",
    "                return -1\n",
    "        return cand\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {}\n",
    "\n",
    "    def cache_knows(self, i, j):\n",
    "        if (i, j) in self.cache:\n",
    "            return self.cache[(i, j)]\n",
    "        else:\n",
    "            self.cache[(i, j)] = knows(i, j)\n",
    "            return self.cache[(i, j)]\n",
    "\n",
    "    def is_celebrity(self, candidate, n):\n",
    "        for i in range(n):\n",
    "            if i == candidate:\n",
    "                continue\n",
    "            if not (self.cache_knows(i, candidate) and not self.cache_knows(candidate, i)):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "\n",
    "        candidate = 0\n",
    "        # loop invariant: (candidate, i) does not contain the celebrity\n",
    "        for i in range(1, n):\n",
    "            # knows(candidate, i) == 0 -> i is not the celebrity\n",
    "            # knows(candidate, i) == 1 -> candidate is not the celebrity\n",
    "            if self.cache_knows(candidate, i) == 1:\n",
    "                candidate = i\n",
    "\n",
    "        if self.is_celebrity(candidate, n):\n",
    "            return candidate\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    # 遇到认识的排除自身，遇到不认识的排除对方，每次调用都能排除一个人（排除他人1次，自己可能需要n-1次）\n",
    "    # 遇到不认识所有人的直接判断其是否符合要求即可（最多n-1次）\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        never = set()\n",
    "        for i in range(n):\n",
    "            if i in never: continue\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if j == i: continue\n",
    "                if knows(i, j):\n",
    "                    break\n",
    "                else:\n",
    "                    never.add(j)\n",
    "                    cnt += 1\n",
    "            if cnt == n - 1:\n",
    "                for k in range(n):\n",
    "                    if k == i: continue\n",
    "                    if not knows(k, i):\n",
    "                        return -1\n",
    "                return i\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "       self.n = n\n",
    "       celebrity_candidate = 0\n",
    "       for i in range(1, n):\n",
    "           if knows(celebrity_candidate, i):\n",
    "               celebrity_candidate = i\n",
    "       if self.is_celebrity(celebrity_candidate):\n",
    "           return celebrity_candidate\n",
    "       return -1\n",
    "\n",
    "    def is_celebrity(self, i):\n",
    "       for j in range(self.n):\n",
    "           if i == j: continue\n",
    "           if knows(i, j) or not knows(j, i):\n",
    "               return False\n",
    "       return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "\n",
    "\n",
    "        candidate = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(candidate, i):\n",
    "                candidate = i\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            if candidate == i: continue\n",
    "\n",
    "            if not knows(i, candidate) or knows(candidate, i):\n",
    "                return -1\n",
    "\n",
    "        return candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for x in range(1,n):\n",
    "            if knows(res, x):\n",
    "                res = x\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i == res:\n",
    "                continue\n",
    "            if knows(res, i):\n",
    "                return -1\n",
    "            if not knows(i, res):\n",
    "                return -1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        # 将所有候选人装进队列\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            q.append(i)\n",
    "        # 一直排除，直到只剩下一个候选人停止循环\n",
    "        while len(q) >= 2:\n",
    "            # 每次取出两个候选人，排除一个\n",
    "            cand = q.pop(0)\n",
    "            other = q.pop(0)\n",
    "            if knows(cand, other) or not knows(other, cand):\n",
    "                # cand 不可能是名人，排除，让 other 归队\n",
    "                q.insert(0, other)\n",
    "            else:\n",
    "                # other 不可能是名人，排除，让 cand 归队\n",
    "                q.insert(0, cand)\n",
    "\n",
    "        # 现在排除得只剩一个候选人，判断他是否真的是名人\n",
    "        cand = q.pop(0)\n",
    "        for other in range(n):\n",
    "            if other == cand:\n",
    "                continue\n",
    "            # 保证其他人都认识 cand，且 cand 不认识任何其他人\n",
    "            if not knows(other, cand) or knows(cand, other):\n",
    "                return -1\n",
    "        # cand 是名人\n",
    "        return cand\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cur = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(cur, i):\n",
    "                cur = i\n",
    "        for i in range(n):\n",
    "            if knows(i, cur) == True and knows(cur, i) == False:\n",
    "                pass\n",
    "            elif i == cur:\n",
    "                pass\n",
    "            else:\n",
    "                cur = -1\n",
    "                break\n",
    "        return cur\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        for cand in range(n):\n",
    "            other = 0\n",
    "            # 保证其他人都认识 cand，且 cand 不认识任何其他人\n",
    "            # 否则 cand 就不可能是名人\n",
    "            while other < n:\n",
    "                if cand == other:\n",
    "                    other += 1\n",
    "                    continue\n",
    "                if knows(cand, other) or not knows(other, cand):\n",
    "                    break\n",
    "                other += 1\n",
    "            if other == n:\n",
    "                # 找到名人\n",
    "                return cand\n",
    "        # 没有一个人符合名人特性\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cand = 0\n",
    "        for other in range(1, n):\n",
    "            if not knows(other, cand) or knows(cand, other):\n",
    "                # cand 不可能是名人，排除\n",
    "                # 假设 other 是名人\n",
    "                cand = other\n",
    "            else:\n",
    "                # other 不可能是名人，排除\n",
    "                # 什么都不用做，继续假设 cand 是名人\n",
    "                pass\n",
    "        # 现在的 cand 是排除的最后结果，但不能保证一定是名人\n",
    "        for other in range(n):\n",
    "            if cand == other:\n",
    "                continue\n",
    "            # 需要保证其他人都认识 cand，且 cand 不认识任何其他人\n",
    "            if not knows(other, cand) or knows(cand, other):\n",
    "                return -1\n",
    "        return cand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            # 判断当前的第i个人是否是名人\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                print(f\"knows = {knows(i, j)}\")\n",
    "                if knows(i, j):\n",
    "                    flag = False\n",
    "                    break\n",
    "                if not knows(j, i):\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(n):\n",
    "                if i == j: continue \n",
    "                if knows(i, j) or not knows(j, i):\n",
    "                    flag = False \n",
    "                    break \n",
    "            if flag: return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        a = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(a, i):\n",
    "                a = i\n",
    "        # b = n-1\n",
    "        # for i in range(n-1):\n",
    "        #     if knows(b, i):\n",
    "        #         b = i\n",
    "        # if a != b:\n",
    "        #     return -1\n",
    "        # 此时a是嫌疑人，因为其他人都排除了，没办法只能逐个验证\n",
    "        # 还有一种可能性：即出现了两个无法辨认的情况，如果出现两个人怎么办\n",
    "        for i in range(n):\n",
    "            if a != i and (knows(a, i) or not knows(i, a)):\n",
    "                    return -1\n",
    "        return a        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        ### solution\n",
    "        # \n",
    "\n",
    "        ## Elimination O(n) O(1)\n",
    "        i = 0\n",
    "        for j in range(1, n):\n",
    "            if knows(i, j):\n",
    "                i = j\n",
    "        for j in range(n):\n",
    "            if i != j and (knows(i, j) or not knows(j, i)):\n",
    "                return -1\n",
    "        return i\n",
    "\n",
    "        ## seen\n",
    "        seen = [True] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if seen[j] and not knows(i, j):\n",
    "                    seen[j] = False\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if seen[i]:\n",
    "                res.append(i)\n",
    "        for i in res:\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if knows(i, j):\n",
    "                    cnt += 1\n",
    "            if cnt == 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        self.n = n\n",
    "        celebrity_candidate = 0\n",
    "        for i in range(1,n):\n",
    "            if knows(celebrity_candidate, i):\n",
    "                celebrity_candidate=i\n",
    "        if self.is_celebrity(celebrity_candidate):\n",
    "           return celebrity_candidate   \n",
    "        return -1\n",
    "\n",
    "    def is_celebrity(self,i):\n",
    "        for j in range(self.n):\n",
    "            if i==j:continue\n",
    "            if knows(i,j) or not knows(j,i):\n",
    "                return False\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            q.append(i)\n",
    "        while len(q) >= 2:\n",
    "            a = q.pop(0)\n",
    "            b = q.pop(0)\n",
    "            if knows(a, b) or not knows(b, a):\n",
    "                q.insert(0, b)\n",
    "            else:\n",
    "                q.insert(0, a)\n",
    "        can = q.pop()\n",
    "        for i in range(n):\n",
    "            if i == can:\n",
    "                continue\n",
    "            if knows(can, i) or not knows(i, can):\n",
    "                return -1\n",
    "        return can"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "       self.n = n\n",
    "       for i in range(n):\n",
    "           if self.is_celebrity(i):\n",
    "               return i\n",
    "       return -1\n",
    "   \n",
    "    def is_celebrity(self, i):\n",
    "        for j in range(self.n):\n",
    "            if i == j: continue # 他们认识自己就不用询问。\n",
    "            if knows(i, j) or not knows(j, i):\n",
    "                return False\n",
    "        return True\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        celeb = 0\n",
    "\n",
    "        # print(knows(0, 1))\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if knows(celeb, i):\n",
    "                celeb = i\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i == celeb:\n",
    "                continue\n",
    "            if knows(celeb, i) or not knows(i, celeb):\n",
    "                return -1\n",
    "        \n",
    "        return celeb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        def is_celebrity(i):\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                if knows(i, j) or not knows(j, i):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ceb = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(ceb, i):\n",
    "                ceb = i\n",
    "            if is_celebrity(ceb):\n",
    "                return ceb\n",
    "        return -1\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        cond = 0\n",
    "        for i in range(1, n):\n",
    "            if knows(cond, i) or not knows(i, cond):\n",
    "                # 排除\n",
    "                cond = i\n",
    "\n",
    "        for i in range(n):\n",
    "            if i == cond:\n",
    "                continue\n",
    "            if knows(cond, i) or not knows(i, cond):\n",
    "                return -1\n",
    "        return cond"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        def is_celebrity(i):\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                if knows(i, j) or not knows(j, i):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            if is_celebrity(i):\n",
    "                return i\n",
    "        return -1\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        rec = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            # i是不是名人，1，他不认识所有人 2所有人认识他\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    kij,kji = -1,-1\n",
    "                    if rec[i][j]!=0:\n",
    "                        kij = rec[i][j]\n",
    "                    else:\n",
    "                        kij = knows(i,j)\n",
    "                        rec[i][j] = kij\n",
    "                    if rec[j][i]!=0:\n",
    "                        kji = rec[j][i]\n",
    "                    else:\n",
    "                        kji = knows(j,i)\n",
    "                        rec[j][i] = kji\n",
    "                    if not (kji and not kij):\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag:\n",
    "                return i\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The knows API is already defined for you.\n",
    "# return a bool, whether a knows b\n",
    "# def knows(a: int, b: int) -> bool:\n",
    "\n",
    "class Solution:\n",
    "    def findCelebrity(self, n: int) -> int:\n",
    "        #indeg=[0]*n\n",
    "        #outdeg=[0]*n\n",
    "        s=set()\n",
    "        for i in range(n):\n",
    "            s.add(i)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and knows(i,j):\n",
    "                    s.remove(i)\n",
    "                    break\n",
    "        #print(indeg,outdeg)\n",
    "        #print(s)\n",
    "        for i in range(n):\n",
    "            find=False\n",
    "            if i in s:\n",
    "                for j in range(n):\n",
    "                    if i!=j and not knows(j,i):\n",
    "                        find=True\n",
    "                        break\n",
    "                if not find:\n",
    "                    return i\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
